﻿#define _CRT_SECURE_NO_WARNINGS

//852. 山脉数组的峰顶索引
//具有二段性——》二分查找
int peakIndexInMountainArray(vector<int>& arr)
{
    //int left = 0, right = arr.size() - 1, mid;
    int left = 1, right = arr.size() - 2, mid;//根据题意，如果有峰值，一定不可能在第一个和最后一个
    while (left < right)
    {
        mid = left + (right - left) / 2;
        if (arr[mid] < arr[mid + 1])
            left = mid + 1;
        else
            right = mid;
    }
    return left;

}
//162. 寻找峰值
int findPeakElement(vector<int>& nums)
{
    int left = 0, right = nums.size() - 1, mid;
    while (left < right)
    {
        mid = left + (right - left) / 2;
        if (nums[mid] < nums[mid + 1])
            left = mid + 1;
        else
            right = mid;
    }
    return left;

}

//153. 寻找旋转排序数组中的最小值
//⼆分的本质：找到⼀个判断标准，使得查找区间能够⼀分为
int findMin(vector<int>& nums)
{
    int left = 0, right = nums.size() - 1, mid;
    int k = nums[right];
    while (left < right)
    {
        mid = left + (right - left + 1) / 2;
        if (nums[mid] > nums[mid - 1])
        {
            if (nums[mid] > k)
                left = mid + 1;
            else
                right = mid - 1;
        }
        else
            return nums[mid];
    }
    return nums[left];
}

//剑指 Offer 53 - II. 0～n-1中缺失的数字
int missingNumber(vector<int>& nums)
{
    int left = 0, right = nums.size(), mid;
    while (left < right)
    {
        mid = left + (right - left) / 2;
        if (nums[mid] == mid)
        {
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }
    return left;

}